/*
剑指 Offer 47. 礼物的最大价值
解题思路：动态规划思想。先初始化第一行和第一列。当前值更新为当前值加上前一行的数或前一列的数。
然后从第二行第一个开始操作，判断当前数左边的数和上边的数那个大，取最大值与当前值相加并更新当
前值，然后向右移动重复前边判断，当这一行判断往后向下一行判断。直到所有位置判断完，返回最后一
行最后一列的数。
 */
public class Offer47 {

  public static void main(String[] args) {
    int[][] num = new int[][]{
            {1,3,1},
            {1,5,1},
            {4,2,1}
    };
    int res = new Offer47().maxValue(num);
    for (int[] ints : num) {
      for (int anInt : ints) {
        System.out.print(anInt + ",");
      }
      System.out.println();
    }
    System.out.println(res);

  }

  public int maxValue(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 1; i < n; i++) {
      grid[0][i] = grid[0][i] + grid[0][i - 1];
    }
    for (int i = 1; i < m; i++) {
      grid[i][0] = grid[i][0] + grid[i - 1][0];
    }
    for(int i = 1; i < m; i++){
      for(int j = 1; j < n; j++){
        grid[i][j] = grid[i][j] + Math.max(grid[i][j - 1], grid[i - 1][j]);
      }
    }
    return grid[m - 1][n - 1];
  }
}
